1. Field of the Invention
The present invention relates to a computer-aided routing method and an apparatus therefor which are used in piping in plants, layout design of ducts and rest rooms, and wiring design of electronic circuits.
2. Description of the Related Art
In recent years, computer-aided design (CAD) systems have been used to shorten time for designing various plants and equipment and reduce labor. Some conventional CAD systems include a routing system for aiding design of routing, i.e., paths in piping design in plants, layout design of equipment, or wiring design of electronic circuits. A typical routing system is described in Japanese Patent Disclosure (Kokai) No. 60-79470 or 62-114061. When piping design in plants by a routing system is exemplified, the routing system has a function of finding best routing, i.e., best piping in a best area in a plant, with an aid of a computer in consideration of restriction conditions such as conditions defined by pipes used, buildings of plants, safety, cost, and the like, and a function of displaying the routing result and drafting a routing plan.
In a conventional routing system, a specific target routing area is found by a general technique shown in a flow chart in FIG. 1. More specifically, when an operator inputs an object area name, a size of a specific target space, and limiting conditions and energizes the routing system, space data of an object area is read out from a memory, and the object area is divided into a plurality of small areas (SA1). The space data read out from the memory are assigned to the corresponding divided areas (SA2), a divided area or divided areas which coincide with the specific target area are found using a routing method such as an A-star algorithm or a lattice development method (maze method) (SA3 and SA4).
The above processing in a two-dimensional space will be briefly described below. As shown in FIG. 2, assume that an object area 1 is selected and that specific piping between points A and B in the object area 1 is ordered. Under these assumptions, the object area 1 is divided into small areas in a mesh-like manner. The length and width of each divided area 2 are determined by a maximum outer diameter of piping. Space data, i.e., data of an obstacle 3, read out from the memory are assigned to the respective divided areas 2. A routing processor extracts the divided areas 4 continuous from the point A to the point B to perform target piping without being interfered by the obstacle 3. The resultant route is the final piping route.
In the conventional routing system employing the above technique, however, when the object area is increased or the specific area size is small, the number of divided areas constituting the object area is very large. As a result, a required memory capacity is greatly increased, and the processing time is prolonged accordingly.
In order to eliminate the above drawbacks, the following conventional methods are proposed: (a) a method of appropriately selecting a start point; (b) a double developing method in which routing is started from both ends of a route to be obtained; (c) a method of appropriately limiting a routing area; and (d) a method of giving a higher priority to a direction closer to a target point during routing. None of these conventional methods, however, cannot greatly reduce the memory capacity.
As described above, in the conventional routing systems, when the object area is increased and the size of the divided areas corresponding to a routing target is decreased, the memory capacity must be increased and the processing time is undesirably prolonged.